package dp;

import java.util.Collections;

//Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
//For example,
//Given:
//s1 ="aabcc",
//s2 ="dbbca",
//When s3 ="aadbbcbcac", return true.
//When s3 ="aadbbbaccc", return false.
public class InterleavingString {

	public static void main(String[] args) {
		System.out.println(isInterleave2("", "", "a"));
	}
	
	//运行时间：48ms
	//占用内存：755k
	//result[i][j]表示的是下标为string1和string2的下标为i和j与string[i + j]是否相等
	//result[i][j] = string3[i + j] == string1[i] && result[i + 1][j]
	//|| string3[i + j] == string2[j] && result[i][j + 1];
	//也就是说如果与两个字符串中的i 、j都相等那么就等于两者结果的或，如果只与一个相等，那么就等于那个结果
	//比如下面的例子
	//aa ab aaba --->  a ab aba 与  aa b aba相或  。 aa b aba  就只等于 a b ba
	public static boolean isInterleave2(String s1, String s2, String s3){
		System.out.println(s1.length() + " " + s2.length() + s3.length());
		if(s3 == null || s1 == null || s2 == null || s3.length() != s1.length() + s2.length()){
			return false;
		}
		//result[i][j]表示以string[i ... length - 1]与string2[j ... length - 1]是否与string3[i +j ....length]相匹配
		boolean[][] result = new boolean[s1.length() + 1][s2.length() + 1];
		char[] string1 = s1.toCharArray();
		char[] string2 = s2.toCharArray();
		char[] string3 = s3.toCharArray();
		result[string1.length][string2.length] = true;
		//初始化边界条件
		for (int j = string2.length - 1; j >= 0; j--) {
			result[string1.length][j] = result[string1.length][j + 1] && string2[j] == string3[s1.length() + j];
		}
		for (int i = string1.length - 1; i >= 0; i--) {
			result[i][string2.length] = result[i + 1][string2.length] && string1[i] == string3[s2.length() + i];
		}
		for (int j = string2.length - 1; j >= 0; j--) {
			for (int i = string1.length - 1; i >= 0; i--) {
				result[i][j] = string3[i + j] == string1[i] && result[i + 1][j]
						|| string3[i + j] == string2[j] && result[i][j + 1];
			}
		}
		for (int i = 0; i <= string1.length; i++) {
			for (int j = 0; j <= string2.length; j++) {
				System.out.print(result[i][j] + "  ");
			}
			System.out.println();
		}
		// Collections.synchronizedMap(m);
		return result[0][0];
	}
}
